//合并两个有序数组

//方法一：直接合并后，排序
//时间复杂度O((m+n)log(m+n))，空间复杂度O((m+n)log(m+n))
class Solution
{
    public:
        void merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
        {
            for(int i = 0; i < n; ++i)
            {
                nums1[m + i] = nums2[i];
            }
            sort(nums1.begin(), nums1.end());
        }
};


//方法二：双指针，相当于归并排序
//时间复杂度O(m+n)，空间复杂度O(m+n)
class Solution {
    public:
        void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
            int arr[m + n]; //数组可以[m+n]这样定义
            int i = 0, j = 0;
            int ans; //定义一个中间变量
            while(i < m || j < n)
            {
                if(i == m)       // i == m && j < n
                    ans = nums2[j++];
                else if(j == n)  // i < m && j == n
                    ans = nums1[i++];
                else if(nums1[i] < nums2[j])   // i < m && nums1[i] < nums2[j]
                    ans = nums1[i++];
                else                           // j < n && nums2[j] < nums1[i]
                    ans = nums2[j++];

                arr[i + j - 1] = ans;  // 1+0-1 = 0;  0+1-1 = 0; 从0下标开始

            }

            for(int i = 0; i < m+n; ++i) //也可以写 i != m+n
            {
                nums1[i] = arr[i];

            }
        }
};

//方法三：逆双指针
//从后往前遍历，nums1后面是空的，将元素从后往前放到nums1中
//时间复杂度O(m+n)，空间复杂度O(1)
class Solution {
    public:
        void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
            int arr[m + n];
            int i = m - 1, j = n - 1; //从后往前遍历
            int cur = m + n - 1;
            int temp;
            while(i >= 0 || j >= 0) //退出条件
            {
                if(i == -1) //相当与m=0，即nums1没有元素
                    temp = nums2[j--];
                else if(j == -1)
                    temp = nums1[i--];
                else if(nums1[i] > nums2[j])
                    temp = nums1[i--];
                else 
                    temp = nums2[j--];

                nums1[cur--] = temp;
            }
        }
};
